Pearls in Graph Theory by Nora Hartsfield & Gerhard Ringel
Author:Nora Hartsfield & Gerhard Ringel
Language: eng
Format: epub, pdf
Publisher: Dover Publications
Published: 1994-06-22T16:00:00+00:00
Notice that if we add the same number, for example 100, to every label in Figure 6.2.4, Kirchhoff’s Current Law still holds at every vertex. If we try this with Figure 6.2.2, it will not work. This leads us to the following definition. A graph G with q edges is called strongly conservative if for every number h there exists a directed labeling of the edges of G with the numbers h+l, h+2,..., h+q such that Kirchhoff’s Current Law holds at every vertex. Thus the graph in Figure 6.2.4 is strongly conservative, while the graph in Figures 6.2.1 and 6.2.2 may or may not be strongly conservative. We cannot say at the moment.
The proof of the following theorem is actually easier than the proof of the corresponding theorem for magic graphs.
Theorem 6.2.3. If G is decomposable into two subgraphs H1 and H2, and if H1 is conservative, and H2 is strongly conservative, then G is conservative. Moreover, if both H1 and H2 are strongly conservative, then G is strongly conservative.
Proof. Let q1 be the number of edges in H1 and q2 the number of edges in h2, so the number of edges in G is q1 + q2. Take a conservative labeling of h1using the numbers 1, 2, 3,..., q1 and a strongly conservative labeling of h2 using the numbers q1 + 1, q1 + 2,..., q1 + q2. In both these labelings Kirchhoff’s Current Law holds, so the directed sum at each vertex is zero in G. Hence we have exhibited a conservative labeling of G.
Now we suppose that both H1 and H2 are strongly conservative, and h is a given number. Take a strongly conservative labeling of the edges of H1 using the numbers h + 1, h + 2,..., h + q1, and a strongly conservative labeling of the edges of H2 using the numbers h +q1 + 1, h + q1 + 2,..., h + q1 + q2. Again, the directed sum at each vertex is zero, and we obtain a strongly conservative labeling of the edges of G using the numbers h + 1, h + 2,..., h + q1 + q2. Thus G is strongly conservative.
Notice that the graph of Theorem 6.2.1 is actually strongly conservative, since the conservative labeling consists of two edges directed in and two edges directed out at each vertex. Hence, adding a constant h to the label of each edge does not affect the directed sum at each vertex.
Theorem 6.2.1*. If G is decomposable into two Hamilton cycles, then G is strongly conservative.
Theorem 6.2.4. If G is a graph with n vertices, where n is odd, and G is decomposable into three Hamilton cycles, then G is strongly conservative.
Proof. Call the three Hamilton cycles H1, H2, and H3. We direct the edges of each of H1, H2, and H3 in such a way that a traveler going around one of these cycles finds all the arrows going in the same direction. See Figures 6.2.5 and 6.2.6. We choose a vertex a and label the edges of H3, beginning at a, by
(H3)a 3n, 3n−6,.
Download
Pearls in Graph Theory by Nora Hartsfield & Gerhard Ringel.pdf
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.
Biomathematics | Differential Equations |
Game Theory | Graph Theory |
Linear Programming | Probability & Statistics |
Statistics | Stochastic Modeling |
Vector Analysis |
Modelling of Convective Heat and Mass Transfer in Rotating Flows by Igor V. Shevchuk(6213)
Weapons of Math Destruction by Cathy O'Neil(5801)
Factfulness: Ten Reasons We're Wrong About the World – and Why Things Are Better Than You Think by Hans Rosling(4470)
Descartes' Error by Antonio Damasio(3150)
A Mind For Numbers: How to Excel at Math and Science (Even If You Flunked Algebra) by Barbara Oakley(3090)
Factfulness_Ten Reasons We're Wrong About the World_and Why Things Are Better Than You Think by Hans Rosling(3034)
TCP IP by Todd Lammle(2995)
Applied Predictive Modeling by Max Kuhn & Kjell Johnson(2885)
Fooled by Randomness: The Hidden Role of Chance in Life and in the Markets by Nassim Nicholas Taleb(2845)
The Tyranny of Metrics by Jerry Z. Muller(2826)
The Book of Numbers by Peter Bentley(2756)
The Great Unknown by Marcus du Sautoy(2522)
Once Upon an Algorithm by Martin Erwig(2465)
Easy Algebra Step-by-Step by Sandra Luna McCune(2445)
Lady Luck by Kristen Ashley(2393)
Practical Guide To Principal Component Methods in R (Multivariate Analysis Book 2) by Alboukadel Kassambara(2368)
Police Exams Prep 2018-2019 by Kaplan Test Prep(2340)
All Things Reconsidered by Bill Thompson III(2248)
Linear Time-Invariant Systems, Behaviors and Modules by Ulrich Oberst & Martin Scheicher & Ingrid Scheicher(2219)
